10285. Где я?

Фермер Джон вышел прогуляться по дороге и думает, что теперь он может заблудиться!

Вдоль дороги в ряд расположены n ферм. К сожалению, на фермах нет номеров домов, поэтому фермеру Джону сложно определить его местоположение на дороге. Однако на каждой ферме есть цветной почтовый ящик на обочине дороги, поэтому фермер Джон надеется, что если он посмотрит на цвета ближайших к нему почтовых ящиков, то сможет однозначно определить, где он находится.

Каждый цвет почтового ящика определяется буквой в диапазоне A..Z, поэтому последовательность n почтовых ящиков может быть представлена строкой длины n из букв A..Z. Некоторые почтовые ящики могут иметь одинаковый цвет. Фермер Джон хочет найти такое наименьшее значение k, чтобы, посмотрев на любую последовательность из k последовательных почтовых ящиков, он смог бы однозначно определить местоположение этой последовательности на дороге.

Пусть последовательность почтовых ящиков вдоль дороги ABCDABC. Фермер Джон не может установить k = 3, поскольку, если он видит ABC, то имеется два возможных места на дороге, где может быть этот последовательный набор цветов. Наименьшее значение k = 4, поскольку, если он смотрит на любой последовательный набор из 4 почтовых ящиков, то эта последовательность цветов однозначно определяет его положение на дороге.

Вход. Первая строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит строку из n символов в диапазоне A..Z.

Выход. Выведите одно целое число – наименьшее значение k, которое решает проблему фермера Джона.

Пример входа	Пример выхода
7 ABCDABC	4

РЕШЕНИЕ

структура данных - set

Анализ алгоритма

Искомое значение k будем искать перебором. Сначала проверим, подходит ли k = 1. Потом проверим k = 2 и так далее пока не будет найдено подходящее.

Расмотрим, как определить будет ли текущее значение k подходящим. Выделим все подстроки длины k из входной строки и занесем их во множество. Число всех подстрок равно n – k + 1. Если оно равно размеру множества, то все подстроки различны и значение k будет подходящим.

Пример

Рассмотрим входную строку “ABCDABC”.

Пусть k = 2. Выделим все подстроки длины 2: AB, BC, CD, DA, AB, BC. Множество подстрок будет иметь вид: {AB, BC, CD, DA}. Всего подстрок длины 2 имеется n – k + 1 = 7 – 2 + 1 = 6. Однако множество содержит 4 элемента, следовательно среди подстрок имеются повторения.

Пусть k = 4. Выделим все подстроки длины 4: ABCD, BCDA, CDAB, DABC. Множество подстрок имеет вид: { ABCD, BCDA, CDAB, DABC }. Всего подстрок длины 4 имеется n – k + 1 = 7 – 4 + 1 = 4. Множество также содержит 4 элемента, значение k = 4 является подходящим.

Реализация алгоритма

Функция can возврщает 1, если все подстроки длины k в строке s различны. Иначе функция возвращает 0.

int can(int k)

{

set<string> x;

Выделяем подстроку длины k начиная с индекса i. Очевидно, что i + k ≤ n.

for (int i = 0; i + k <= n; i++)

{

Если очередная вырезанная подстрока s.substr(i, k) уже имеется во множестве x, то возвращаем 0.

if (x.count(s.substr(i, k)) > 0) return 0;

Заносим подстроку во множество x.

x.insert(s.substr(i, k));

}

Одинаковые подстроки не встретились, возвращаем 1.

return 1;

}

Основная часть программы. Читаем входные данные.

cin >> n >> s;

Перебираем k = 1, 2, 3, … и проверяем в функции can является ли оно подходящим значением. Как только искомое значение k будет найдено, выходим из цикла.

for (k = 1; ; k++)

if (can(k)) break;

Выводим ответ.

cout << k << "\n";